#include <queue>
#include <unordered_map>
#include <vector>

#include "grid.hpp"

using namespace std;

// priority_queue是STL提供的一种容器适配器，内部实现默认是最大堆
// PQElement是队列中的元素类型，vector<PQElement>是底层容器类型
// greater<PQElement>是函数对象（functor），用于实现大于（>）比较
// priority_queue中，如果比较函数 comp(a, b) 返回 true，则表示a的优先级低于b，因此a会被放到b的后面；与greater<>结合，就形成了小根堆，数值较小的会被放到前面）
typedef pair<double, Location> PQElement;
typedef priority_queue<PQElement, vector<PQElement>, greater<PQElement>> PQLoc;

// 定义了1个函数指针类型heuristic_fn，指针指向一个接受两个Location参数并返回double类型的函数。
typedef double(heuristic_fn)(const Location&, const Location&);


Location jump(const Grid& grid, const Location initial, const Location dir, const Location goal);

vector<Location> successors(const Grid& grid, const Location& current, const Location& parent, const Location& goal);

unordered_map<Location, Location> jps(const Grid& grid, const Location& start, const Location& goal, heuristic_fn heuristic);
